// https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/
// Created by ade on 2022/9/6.
//
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>


using namespace std;

class Solution {
public:
    int uniqueLetterString(string s) {
        unordered_map<char, vector<int>> index;
        for (int i = 0; i < s.size(); i++) {
            index[s[i]].emplace_back(i);
        }
//        for (auto i : index) {
//            cout << i.first << " ";
//            for (auto j : i.second) {
//                cout << j << ",";
//            }
//            cout << endl;
//        }
        int res = 0;
        for (auto &&[_, arr]: index) {
            arr.insert(arr.begin(), -1);
            arr.emplace_back(s.size());
            for (int i = 1; i < arr.size() - 1; i++) {
                res += (arr[i] - arr[i - 1]) * (arr[i + 1] - arr[i]);
            }
        }
        return res;
    }
};

int main() {
    Solution so;
    cout << so.uniqueLetterString("aba");
    return 0;
}